'''
Created on 31/07/2011

@author: Digao
'''
def toInt(arg):
    return int(arg)

def toStr(a,b):
    return str(a)+' '+str(b)

MATCH = 'welcome to code jam'

mem = {}
def numberF(str,strI,match,matchI):
    if (strI,matchI) in mem:
        return mem[(strI,matchI)]
    if matchI==0:
        res = str[:strI+1].count(match[0])
    elif strI==0:
        res=0
    elif str[strI]==match[matchI]:
        res = (numberF(str,strI-1,match,matchI-1)+numberF(str,strI-1,match,matchI))%10000
    else:
        res = numberF(str,strI-1,match,matchI)
    mem[(strI,matchI)]=res
    return res
    pass

input = open('input.in')
CASES = int(input.readline())
for case in range(1,CASES+1):
    phrase = input.readline().strip()
    mem={}
    ans = numberF(phrase,len(phrase)-1,MATCH,len(MATCH)-1)
    ans = ('0000'+str(ans))[-4:]
    print 'Case #%d: %s'%(case,ans)
    


